mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, Slater's condition (or Slater condition) is a sufficient condition for strong duality to hold for a convex optimization problem, named after Morton L. Slater. Informally, Slater's condition states that the

feasible region In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potent ...

must have an

interior point In mathematics, specifically in topology, the interior of a subset of a topological space is the union of all subsets of that are open in . A point that is in the interior of is an interior point of . The interior of is the complement of t ...

(see technical details below). Slater's condition is a specific example of a

constraint qualification Constraint may refer to: * Constraint (computer-aided design), a demarcation of geometrical characteristics between two or more entities or solid modeling bodies * Constraint (mathematics), a condition of an optimization problem that the solution ...

. In particular, if Slater's condition holds for the

primal problem In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. If the primal is a minimization problem then th ...

, then the

duality gap In optimization problems in applied mathematics, the duality gap is the difference between the primal and dual solutions. If d^* is the optimal dual value and p^* is the optimal primal value then the duality gap is equal to p^* - d^*. This value ...

is 0, and if the dual value is finite then it is attained.

Formulation

Consider the

optimization problem In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables ...

\text\; f_0(x)

\text\

f_i(x) \le 0 , i = 1,\ldots,m

Ax = b

where

f_0,\ldots,f_m

are

convex functions In mathematics, a real-valued function is called convex if the line segment between any two points on the graph of the function lies above the graph between the two points. Equivalently, a function is convex if its epigraph (the set of poin ...

. This is an instance of

convex programming Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization pro ...

. In words, Slater's condition for convex programming states that strong duality holds if there exists an

x^*

such that

x^*

is strictly feasible (i.e. all constraints are satisfied and the nonlinear constraints are satisfied with strict inequalities). Mathematically, Slater's condition states that strong duality holds if there exists an

x^* \in \operatorname(D)

(where relint denotes the

relative interior In mathematics, the relative interior of a set is a refinement of the concept of the interior, which is often more useful when dealing with low-dimensional sets placed in higher-dimensional spaces. Formally, the relative interior of a set S (de ...

of the convex set

D := \cap_^m \operatorname(f_i)

) such that :

f_i(x^*) < 0, i = 1,\ldots,m,

(the convex, nonlinear constraints) :

Ax^* = b.\,

Generalized Inequalities

Given the problem :

\text\; f_0(x)

\text\

f_i(x) \le_ 0 , i = 1,\ldots,m

Ax = b

where

f_0

is convex and

f_i

K_i

-convex for each

i

. Then Slater's condition says that if there exists an

x^* \in \operatorname(D)

such that :

f_i(x^*) <_ 0, i = 1,\ldots,m

and :

Ax^* = b

then strong duality holds.

References

{{Reflist Convex optimization